///1.二维
class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum =0;
        int maxnum =0;
        for(auto& e: nums)  {
            sum+=e;
            maxnum = max(maxnum, e);
        }
        int n = nums.size();
        if(sum%2 == 1 || n <2)
            return false;

        int target = sum/2;
        if(maxnum > target)
            return false;
        
        vector<vector<int>> dp(n+1, vector<int> (target+1, 0));
        for(int i = 0; i <= n; ++i) {
            dp[i][0] = true;
        }
        for(int i = 1; i <= n; ++i) {
            for(int j = 1; j <= target; ++j) {
                if(nums[i-1] > j)
                    dp[i][j] = dp[i-1][j];
                else {
                    dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i-1]];
                }
            }
        }
        return dp[n][target];
        
    }
};
//2.一维dp
class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum =0;
        int maxnum =0;
        for(auto& e: nums)  {
            sum+=e;
            maxnum = max(maxnum, e);
        }
        int n = nums.size();
        if(sum%2 == 1 || n <2)
            return false;

        int target = sum/2;
        if(maxnum > target)
            return false;

        
        vector<int> dp(target+1, 0);
        dp[0] = 1;
        for(int i = 0; i < n; ++i) {
            int num = nums[i];
            for(int j = target; j >= 0; --j) {
                if(nums[i] > j) {
                    dp[j] = dp[j]; //多此一举！
                }
                else {
                    dp[j] = dp[j] || dp[j-num];
                }
            }
        }
        
        
        return dp[target];
        
    }
};
//3.一维dp优化
class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int n = nums.size();
        if (n < 2) {
            return false;
        }
        int sum = 0, maxNum = 0;
        for (auto& num : nums) {
            sum += num;
            maxNum = max(maxNum, num);
        }
        if (sum & 1) {
            return false;
        }
        int target = sum / 2;
        if (maxNum > target) {
            return false;
        }
        vector<int> dp(target + 1, 0);
        dp[0] = true;  //dp[j] 表示是否能用已处理过的那些数，凑出和 j
        for (int i = 0; i < n; i++) {
            for (int j = target; j >= nums[i]; --j) { //只能从后往前进行遍历，dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i-1]];   dp[i-1][j-nums[i-1]]这个不知道前面何时覆盖了
                dp[j] |= dp[j - nums[i]];
            }
        }
        return dp[target];
    }
};
/*
二维 DP：真的存了一个表，每一行代表“用前 i 个数”。

一维 DP：只存一行，但通过“从大到小更新”来保证这一行在逻辑上等价于二维的“上一行”。

所以你可以理解为：一维 DP 的初始状态就是二维 DP 的第一行，然后每次迭代相当于生成新的一行，覆盖旧的一行。
*/

